package heap

//堆排序
func HeapSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	//将数组转为最大堆
	_heapify(nums)

	//第一位是数组最大值，交换到最后；然后下沉第一个元素，使得前i个元素保持最大堆
	for i := len(nums) - 1; i >= 1; i-- {
		_swap(nums, 0, i)
		_shiftDown(nums, 0, i)
	}
}

func _heapify(nums []int) {
	n := len(nums)
	for i := _parent(n - 1); i >= 0; i-- {
		_shiftDown(nums, i, n)
	}
}

func _parent(i int) int {
	if i == 0 {
		panic("root has no parent")
	}
	return (i - 1) / 2
}

func _leftChild(i int) int {
	return 2*i + 1
}

func _rightChild(i int) int {
	return 2*i + 2
}

func _shiftDown(vals []int, i int, limit int) {
	//limit表示取vals的前limit个元素作为二叉堆
	n := limit
	for _leftChild(i) < n {
		//先取左子节点
		childIndex := _leftChild(i)
		child := vals[childIndex]
		if _rightChild(i) < n {
			//如果有右子节点，取两个子节点中最小的
			rightChildIndex := _rightChild(i)
			rightChild := vals[rightChildIndex]
			if _cmp(rightChild, child) < 0 {
				child = rightChild
				childIndex = rightChildIndex
			}
		}
		//如果子节点比当前节点小，就交换
		if _cmp(child, vals[i]) < 0 {
			_swap(vals, childIndex, i)
			i = childIndex
		} else {
			break
		}
	}
}

func _swap(vals []int, i, j int) {
	vals[i], vals[j] = vals[j], vals[i]
}

func _cmp(a, b int) int {
	//比较器函数
	return b - a
}
